Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. Hyperelliptic curve cryptography (HECC) is a similar approach which is based on hyperelliptic curves over finite fields.
An elliptic curve (EC) modulo p may be defined as the set of points P=(x,y) satisfying the curve equation y2=x3+ax+b (mod p), where a and b are constant (satisfying 4a3+27b2!=0 (mod p)), plus a “point at infinity” O. With a suitable definition of addition of points P+Q (and doubling 2P=P+P as being a special case of addition when two points are equal) together with the zero point O, this forms an additive group.
Scalar multiplication of a point P by a number k is defined as the result of adding point P to itself k times: kP=P+P+ . . . +P (k times). The elliptic curve discrete logarithm problem is then defined as follows: given the prime modulus p, the curve constants a and b, and two points P and Q, find a number k such that Q=kP. This problem is infeasible for secure elliptic curves for large enough values of p, and thus scalar multiplication is the basic cryptographic operation of an elliptic curve ECk(P)=kP.
Because it is a one-way function, ECk(P) is widely used in common and well-defined cryptographic applications such as encryption and decryption, digital signature generation and verification, key agreement, and key transport to form elliptic curve cryptography variants of those applications.
A hyperelliptic curve (HEC) of genus g over Zp is defined as the set of points P=(x,y) satisfying the curve equation y2+R(x)y=Q(x) (mod p), where R(x) and Q(x) are monatomic polynomials over Zp, and for some integer g—called the genus of the curve—R has a degree that does not exceed g, and Q has a degree of 2g+1. Special conditions for R and Q need to be satisfied for the curve to be nonsingular.
Similar to that as described above in regard to elliptic curves, an additive group can also be associated with hyperelliptic curves. This group is formed with all so-called reduced divisors. A reduced divisor is a pair D of polynomials U(x) and T(x), D=(U,T), with deg(T)<deg(U)<=g such that T2+R(x)T=Q(x) (mod U(x)).
With a suitable definition of an addition operation of divisors D1+D2, this forms an additive group. Scalar multiplication of a group element (divisor) D by a number k is defined as the result of adding D to itself k times: kD=D+D+ . . . +D (k times).
The hyperelliptic curve discrete logarithm problem is defined in a similar way as that for the elliptic curve described above: given a nonsingular hyperelliptic curve and two group elements (divisors) D1 and D2, find a number k such that D1=k D2. This problem is infeasible for a secure hyperelliptic curve for which the group order is divisible by a sufficiently large prime number, and thus scalar multiplication is the basic cryptographic operation of hyperelliptic curve based cryptography.
What is needed, therefore, is a cryptographic arithmetical module that provides acceleration for computation of the cryptographic primitives or provides full implementation of the cryptographic protocols based on elliptic curve cryptography (ECC) or hyperelliptic curve cryptography (HECC).